package _back_tracking

import org.junit.Assert
import org.junit.Test

/**
 * 1980. 找出不同的二进制字符串
 *
 * https://leetcode.cn/problems/find-unique-binary-string/description
 * 题型： 回溯 - 全排列
 * 次题目不需要去重
 * ```
 * 给你一个字符串数组 nums ，该数组由 n 个 互不相同 的二进制字符串组成，且每个字符串长度都是 n 。请你找出并返回一个长度为 n 且 没有出现 在 nums 中的二进制字符串。如果存在多种答案，只需返回 任意一个 即可。
 *
 * 示例 1：
 * 输入：nums = ["01","10"]
 * 输出："11"
 * 解释："11" 没有出现在 nums 中。"00" 也是正确答案。
 * 示例 2：
 *
 * 输入：nums = ["00","01"]
 * 输出："11"
 * 解释："11" 没有出现在 nums 中。"10" 也是正确答案。

 * 示例 3：
 * 输入：nums = ["111","011","001"]
 * 输出："101"
 * 解释："101" 没有出现在 nums 中。"000"、"010"、"100"、"110" 也是正确答案。
 *
 * 提示：
 * n == nums.length
 * 1 <= n <= 16
 * nums[i].length == n
 * nums[i] 为 '0' 或 '1'
 * nums 中的所有字符串 互不相同
 * ```
 */
class leetcode_1980 {
    @Test
    fun test_1() {
        val actual = findDifferentBinaryString(arrayOf("01", "10"))
        val expected = arrayOf("11", "00")
        Assert.assertTrue(expected.contains(actual))
    }

    @Test
    fun test_2() {
        val actual = findDifferentBinaryString(arrayOf("00", "01"))
        val expected = arrayOf("11", "10")
        Assert.assertTrue(expected.contains(actual))
    }

    @Test
    fun test_3() {
        val actual = findDifferentBinaryString(arrayOf("111", "011", "001"))
        val expected = arrayOf("101", "000", "010", "100", "110")
        Assert.assertTrue(expected.contains(actual))
    }

    fun findDifferentBinaryString(nums: Array<String>): String {
        /**
        回溯 - 全排列
        思路： 当path 的 长度 等于 n 时，收集结果
         */
        collect(nums, charArrayOf('0', '1'), "")
        return result
    }

    var result: String = ""
    fun collect(nums: Array<String>, chars: CharArray, path: String) {
        // 1 确定函数参数以及返回值

        // 2 确定终止条件
        if (nums.isEmpty()) {
            return
        }
        if (result != "") {
            return
        }

        // 收集结果
        if (path.length == nums[0].length) {
            if (!nums.contains(path)) {
                result = path
            }
            return
        }

        // 3 确定单层循环的处理逻辑
        for (i in 0 until chars.size) {
            // 处理节点
            val newPath: String = path + chars[i]

            // 递归
            collect(nums, chars, newPath)

            // 回溯
            // 剪枝？去重？
        }
    }
}